#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 5e5 + 10;
const int K = (1 << 30) - 1;

int val[N * 19], ls[N * 19], rs[N * 19];
int n, m, p[N], q[N], res, ndn = 1;
int B;

void add(int &x, int xl, int xr, int v, int l = 0, int r = B - 1) {
	if(!x) x = ++ndn; if(xl <= l && xr >= r) return val[x] = (val[x] + v) & K, void(); int mid = l + r >> 1;
	if(xl <= mid) add(ls[x], xl, xr, v, l, mid);
	if(xr > mid) add(rs[x], xl, xr, v, mid + 1, r);
}

int query(int x, int xl, int xr, int l = 0, int r = B - 1) {
	cerr << l << " " << r << " " << val[x] << endl;
	if(!x) return 0; if(xl <= l && xr >= r) return (1ll * val[x] * (r - l + 1)) & K; int mid = l + r >> 1;
	int ret = (1ll * (min(xr, r) - max(xl, l) + 1) * val[x]) & K;
	if(xl <= mid) ret = (ret + query(ls[x], xl, xr, l, mid)) & K;
	if(xr > mid) ret = (ret + query(rs[x], xl, xr, mid + 1, r)) & K;
	return ret;
}

int main() {
#ifdef YJR_2333_TEST
	freopen("1.in", "r", stdin);
#endif
	n = in, m = in; B = 1 << m; rep(i, 1, n) p[i] = in, q[i] = in;
	int rt = 1;
	rep(i, 1, n) {
		p[i] = (p[i] + res) & (B - 1);
		q[i] = (q[i] + res) & (B - 1);
		int l, r; tie(l, r) = minmax(p[i], q[i]);
		cerr << "Q: " << i << " " << l << " " << r << endl;
		add(rt, l, r, i); res = (res + query(rt, l, r)) & K;
		cerr << res << "!" << endl;
	} cout << res << endl;
	return 0;
}
